We shall now relax the assumption that we may tabulate each state-action pair in a map. In particular, we now apply the techniques of stochastic gradient descent (SGD).
We first describe our value and error functions.
For the sake of generality, we shall parameterize \(\hat{v}(s, w)\) instead of specifying it directly. For example, we may have a linear function \(\hat{v} = x(s)^Tw\), or even a neural network.
Then, we shall try to reach the VE Optimum, or "Value Error Optimum", which is the minimum of
\[ \mathrm{VE}(w) = \sum_{s \in \mathcal{S}} \mu(s) [ v_pi(s) - \hat{v}(s, w) ]^2 \]the least squares error between our estimate and the real value function.
Note that we shall weight it by \(\mu(s)\), or the frequency of visiting a state \(s\).
Now, we apply the SGD algorithm to minimize the squared error. However, as we cannot directly observe \(v_\pi(s)\), we shall use another estimate, namely \(U_t\).
If \(\mathbb{E}[U_t|s] = v_\pi(s)\), or when \(U_t\) is an unbiased estimator, then we will reach the optimum. However, for the remainder of this article, we shall bootstrap,
\[ U_t = \sum_{k=0}^{n-1} \gamma^k g_{t + k} + \gamma^n \hat{v}(s_{t + n}) \]and thus, our update rule becomes
\begin{align} w &\xleftarrow{} w + \alpha \nabla_w (U_t - \hat{v}(s_t))^2 \\ w &\xleftarrow{} w + \alpha' (U_t - \hat{v}(s_t)) \nabla_w \hat{v}(s_t) \\ &\xleftarrow{} w + \alpha' (\sum_{k=0}^{n-1} \gamma^k g_{t + k} + \gamma^n \hat{v}(s_{t + n}) - \nabla_w \hat{v}(s_t)) \end{align}Further, when we use a linear value function \(\hat{v}\) and setting \(n=1\), then
\begin{align} w &\xleftarrow{} w + \alpha (U_t - \hat{v}(s_t)) \nabla_w \hat{v}(s_t) \\ &\xleftarrow{} w + \alpha (x(s)^Tw - \hat{v}(s_t)) x(s) \end{align}Also, recall that because we are sampling based on trajectories, the \(\mu(s)\) term in error function is implicit.
The simple SGD algorithm applied to TD learning aas shown above assumes that \(\mathcal{A}(s)\) isn't large. If it is large, or even continuous, then we need to apply Policy Gradient Methods, see Chapter Six.
Finally, we describe certain ways to create the feature vector \(x(S)\)